/**
-std=c99 
*/

#include <stdio.h>
#include <stdlib.h>
#define N 6
#define K 11

// 信息表：a[1...i] 能否 有一组数和为 k（i<=N, k<K）
int subset[N][K];

// 填写信息表
void dp_subSetSum(int arr[], int k);

// 交换函数
void swap(int* a, int* b);
// 快速排序
void quickSort(int arr[], int head, int tail);

// 拿到结果（不存在则没有输出）
int* getMinSet(int arr[], int k);

int main(int argc, const char* argv[]) {
	int arr[N] = {3, 34, 4, 12, 5, 2};
	int k = K - 1;
	int* set = NULL;
	quickSort(arr, 0, N - 1);
	dp_subSetSum(arr, k);
	set = getMinSet(arr, k);

	// 题示
	fprintf(stdout, "arr[%d]: ", N);
	for (int i = 0; i < N; ++i) {
		fprintf(stdout, "%d ", arr[i]);
	}
	fprintf(stdout, "\nfind subsqe sum equals k=%d\n", k);

	// subset table
	fprintf(stdout, "\nsubset[%d][%d]: \n", N, K);
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) {
			fprintf(stdout, "%d ", subset[i][j]);
		}
		fprintf(stdout, "\n");
	}

	// 结果
	fprintf(stdout, "result set[]: ");
	for (int i = 0; set[i] != 0; ++i) {
		fprintf(stdout, "%d ", set[i]);
	}

	return 0;
}

void dp_subSetSum(int arr[], int k) {
	for (int i = 0; i < N; ++i) {
		subset[i][0] = 1;
	}
	for (int j = 0; j < K; ++j) {
		subset[0][j] = 0;
	}
	// 第一个元素可得到的结果
	if (arr[0] <= k) subset[0][arr[0]] = 1;
	
	for (int i = 1; i < N; ++i) {
		for (int j = i; j < K; ++j) {
			if (arr[i] > j)
				subset[i][j] = subset[i -1][j];
			else {
				int a = subset[i - 1][j - arr[i]];
				int b = subset[i - 1][j];
				subset[i][j] = a | b;
			}
		}
	}
}

int* getMinSet(int arr[], int k) {
	int* set = (int*)calloc(N, sizeof(int));
	int i = N - 1;
	int n = 0;
	while (arr[i] > k) --i;
	
	if (subset[i][k] == 1) {  // 确定有没有这样的一组数,有再去找
		while (k != 0 && i != 0) {
			// 优先选取较大值
			if (subset[i-1][k - arr[i]] == 1) {
				set[n++] = arr[i];
				k -= arr[i];
			}
			--i;
		}
	}
	// 第0行可能直接得到结果值
	if (arr[i] == k) set[n] = arr[i];

	return set;
}

void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void quickSort(int* arr, int head, int tail) {
	int i = head;
	int j = tail;
	int key = arr[head];
	while (i < j) {
		while (i < j && arr[j] >= key) --j;
		while (i < j && arr[i] <= key) ++i;
		if (i < j) swap(&arr[i], &arr[j]);	
	}
	swap(&arr[head], &arr[i]);
	if (i - 1 > head) quickSort(arr, head, i - 1);
	if (i + 1 < tail) quickSort(arr, i + 1, tail);
}
